题解 牛客练习赛6 手铐

发表于 | 更新于

链接：牛客练习赛6手铐

$Description$

给你一个连通无向图，保证每个点最多属于一个简单环，每个点度数最多为$3$，求这个图有多少“手铐图形个数”

其中“手铐图形个数”，定义为三元组$(x,y,S)$，其中$x$和$y$表示图上的两个点，$S$表示一条$x$到$y$的简单路径，而且必须满足：

$1.x$和$y$分别在两个不同的简单环上

$2.x$所在的简单环与路径$S$的所有交点仅有$x,y$所在的简单环与路径$S$的所有交点仅有$y$。

$(x,y,S)$与$(y,x,S)$算同一个手铐

$Solution:$

我们考虑把环给缩掉，缩了之后的点叫做方点，然后本来树上的点叫做圆点

缩完后变成

首先手铐两端都必须是一个方点，然后可以发现如果一条两端都是方点的路径上总共有$x$个方点(不包括两端的方点)，则这两个端点可以构成$2^{x}$个手铐（每次可以走两端）

如图这构成了4个手铐

由于无向图缩点后一定形成一棵树，我们考虑对于生成的这个树进行树形$DP$用$f[u]$表示以$u$为根的子树，到$u$构成的“一半的手铐”的数量
也就是说这样的：

半手铐维护的方法就是

如果u是圆点，则$f[u]=\sum f[v]$;

如果u是方点，则$f[u]=(\sum f[v])\times 2 + 1$;

因为下面上来的每个半手铐都可以走两个方向，然后这个点也可以作为一个半手铐的端点

在跑树形$DP$时顺便统计答案。

对于每个节点$u$,我们强制它的贡献就是手铐的两端在它的两颗子树中，或是一个在子树中，一个是它自己。

对于手铐的两端在它的两颗子树中，只要算出$\frac{\sum f[v]\times(sum-f[v])}{2}$即可

当节点$u$是方点时，贡献还要$\times 2$再加上所有子树中的半手铐个数(即$u$节点与子树中半手铐匹配)

$Code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
#define int long long
#define re register
#define inf 0x3f3f3f3f
#define N 2003000
#define mod 19260817
using namespace std;
struct node{
    int to,next;
}e[N<<1];
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
int n,m,u[N],v[N],cnt=1,head[N],dfn[N],low[N],ans,f[N],st[N],top,num,col,w[N],color[N];
inline int inv2(){return (mod-mod/2)%mod;}
inline void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void Tarjan(int u,int E){
    dfn[u]=low[u]=++num;
    st[++top]=u;
    for (int i=head[u];i;i=e[i].next){
        if (i==(E^1))continue;
        int v=e[i].to;
        if (!dfn[v]){
            Tarjan(v,i);
            low[u]=min(low[u],low[v]);
        }else if (!color[v])
            low[u]=min(low[u],dfn[v]);
    }
    if (low[u]==dfn[u]){
        ++col;
        do{
            ++w[col];color[st[top--]]=col;
        }while (st[top+1]!=u);
    }
}
void dfs1(int u,int fa){
    for (int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if (v==fa)continue;
        dfs1(v,u);
        f[u]=(f[u]+f[v]*w[u]%mod)%mod;
    }
    f[u]+=w[u]==2;
}
void dfs(int u,int fa){
    int res=0,sum=(w[u]==2?(f[u]-1)*inv2()%mod:f[u]);
    for (int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if (v==fa)continue;
        dfs(v,u);
        res=(res+w[u]*f[v]%mod*((sum-f[v]+mod)%mod))%mod;
    }
    ans=(ans+res*inv2()%mod)%mod;
    if (w[u]==2)ans=(ans+sum)%mod;
}
signed main(){
    n=read(),m=read();
    for (int i=1;i<=m;++i){
        u[i]=read(),v[i]=read();
        add(u[i],v[i]);add(v[i],u[i]);
    }
    for (int i=1;i<=n;++i)
        if (!dfn[i])
            Tarjan(i,0);
    for (int i=1;i<=col;++i)w[i]=(w[i]>1)+1;
    memset(head,0,sizeof(head));cnt=0;
    for (int i=1;i<=m;++i)
        if (color[u[i]]!=color[v[i]]){
            add(color[u[i]],color[v[i]]);
            add(color[v[i]],color[u[i]]);
        }
    dfs1(1,0);
    dfs(1,0);
    cout<<ans;
    return 0;
}